package cn.ihna.demo.algorithm.basic;

import cn.ihna.demo.algorithm.util.ArrayUtil;

import java.util.LinkedList;

/**
 * 最长公共子串问题
 *
 * @author xianyingda@gmail.com
 * @serial
 * @since 2020-08-28 14:25
 */
@SuppressWarnings({"Duplicates"})
public class LCS1 {

    private static final String s1 = "123456";
    private static final String s2 = "f345a67";

    public static void main(String[] args) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        int l1 = c1.length;
        int l2 = c2.length;
        int[][] arr = new int[l1 + 1][l2 + 1];
        int i = 0, j = 0, max = 0;
        for (int m = 1; m <= l1; m++) {
            for (int n = 1; n <= l2; n++) {
                if (c1[m - 1] == c2[n - 1]) {
                    // 如果match 值为左上角+1
                    int count = (arr[m][n] = arr[m - 1][n - 1] + 1);
                    if (count > max) {
                        max = count;
                        i = m;
                        j = n;
                    }
                } else {
                    // 要求连续子串 所以数量归零
                    arr[m][n] = 0;
                }
            }
        }
        ArrayUtil.printArr(arr);
        // 矩阵中的数字代表了字符串的这个位置（包含）之前的字符串最长的公共子序列的元素的个数
        LinkedList<String> list = new LinkedList<>();
        while (i > 0 && j > 0) {
            // 从记录的最大值处向上查找即可获得最长子串
            list.addFirst(String.valueOf(c1[i - 1]));
            i = i - 1;
            j = j - 1;
            if (arr[i][j] == 0) {
                break;
            }
        }
        System.out.println(String.join("", list));
    }

}
